package com.rayboo.example.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序（直接插入排序）
 *
 * @author ray
 * @since 2019/08/01
 *
 * <p>通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。
 * 每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成。
 *
 * <p>https://www.cnblogs.com/xiaoming0601/p/5862793.html
 * <p>https://www.runoob.com/w3cnote/insertion-sort.html
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {10, 2, 13, 4, 5, 6, 22, 17, 8};
        System.out.println("排序前：\n" + Arrays.toString(arr));

        new InsertionSort().insertSort(arr);
        System.out.println("排序后：\n" + Arrays.toString(arr));

        new InsertionSort().insertSortDesc(arr);
        System.out.println("排序后（DESC）：\n" + Arrays.toString(arr));
    }

    /**
     * 插入排序
     *
     * @param arr 数组
     */
    public int[] insertSort(int[] arr) {
        int i, j;
        int target;

        //假定第一个元素被放到了正确的位置上
        //这样，仅需遍历1 - arr.length-1
        for (i = 1; i < arr.length; i++) {
            j = i;
            target = arr[i];

            while (j > 0 && target < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            arr[j] = target;
        }

        return arr;
    }

    /**
     * 插入排序（倒序）
     *
     * @param arr 数组
     */
    public int[] insertSortDesc(int[] arr) {
        int i, j;
        int target;

        for (i = 1; i < arr.length; i++) {
            j = i - 1;
            target = arr[i];

            while (j >= 0 && arr[j] < target) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = target;
        }

        return arr;
    }

    /**
     * 排序
     *
     * @param arr 数组
     * @return 排序后的数组
     */
    public static int[] sort(int[] arr) {
        int i, j;
        int temp;

        // 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
        for (i = 1; i < arr.length; i++) {
            // 取出第i个数，和前i-1个数比较后，插入合适位置
            temp = arr[i];

            // 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
            for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                arr[j + 1] = arr[j];
            }

            arr[j + 1] = temp;
        }

        return arr;
    }

}
